package niukejianzhioffer.alg1_10;

/**
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
 * 判断数组中是否含有该整数
 *
 * 输入
 * 复制
 * 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
 * 返回值
 * 复制
 * true
 *
 * 102
 * [[1,2,4,6,8,10,11,13,15,17,20,22,24,27,30,32,35,36,38,39,42,44,46,47,48,49,51,54,55,56],
 * [3,4,6,8,11,13,15,18,19,20,23,25,27,29,33,36,38,41,42,45,48,50,53,54,57,60,63,65,66,67],
 * [5,7,8,11,14,15,17,19,21,23,24,28,31,33,36,39,41,44,47,49,52,53,56,57,60,63,66,68,71,72],
 * [7,10,13,14,17,19,22,25,26,27,30,32,34,37,39,42,44,46,50,53,55,56,59,61,64,66,69,72,74,76],
 * [8,12,16,17,20,21,23,26,29,31,33,35,37,40,42,45,48,49,52,55,58,59,61,63,67,69,70,74,76,79],
 * [10,15,18,20,22,24,27,30,32,33,36,38,39,41,45,47,50,53,56,58,61,64,65,68,69,71,73,76,79,82],
 * [13,17,20,23,24,26,28,31,34,36,38,41,42,43,48,50,53,56,58,61,64,67,68,71,73,74,75,78,81,84],
 * [15,19,22,24,26,28,31,34,35,38,41,44,45,46,49,51,56,59,61,64,67,69,71,73,76,78,79,82,85,87],
 * [17,20,23,26,29,30,32,37,40,42,43,47,50,53,55,56,58,62,64,66,69,72,75,78,80,81,83,86,88,90],
 * [18,21,25,28,30,32,35,38,42,43,44,49,51,55,58,59,61,65,68,71,73,74,77,79,82,85,88,89,91,93],
 * [20,23,28,29,33,36,37,40,43,45,47,52,55,58,60,62,63,66,70,74,76,77,79,81,85,88,89,91,93,94],
 * [23,25,31,33,35,39,42,43,44,46,50,53,56,61,62,65,68,69,72,75,78,81,82,83,88,91,92,93,96,99],
 * [26,27,33,34,38,40,45,48,51,53,55,56,58,64,66,69,72,75,77,80,82,84,87,88,90,93,94,95,99,101],
 * [29,30,36,38,40,42,47,50,53,56,57,59,62,65,68,71,73,77,79,83,84,86,88,91,93,96,99,100,102,103],
 * [32,33,39,42,44,46,49,53,56,59,62,65,68,71,72,75,77,78,80,85,87,90,92,94,96,99,101,103,105,107],
 * [35,37,42,43,46,48,51,55,59,61,65,67,71,74,76,78,81,82,84,86,90,92,95,96,99,102,103,106,107,109],
 * [36,39,43,46,49,50,53,58,62,65,67,70,73,76,77,79,84,87,88,90,93,96,99,102,103,106,108,111,112,115],
 * [38,42,45,47,52,55,57,60,64,66,69,72,75,78,80,82,87,89,91,92,94,99,100,103,105,107,111,112,115,118],
 * [39,44,48,49,55,57,60,63,66,69,72,75,78,80,82,85,89,92,94,95,98,101,102,105,108,111,112,115,116,120],
 * [40,47,49,52,56,59,63,64,68,71,75,78,80,83,85,88,91,94,97,99,101,104,105,108,110,112,115,118,120,123],
 * [42,50,53,55,59,62,66,67,71,73,78,81,82,86,87,90,94,97,100,101,104,106,107,109,111,114,117,120,123,126],
 * [43,51,55,58,62,64,69,71,74,77,81,84,86,87,89,93,96,99,102,103,105,108,111,112,113,116,120,122,125,129],
 * [45,54,56,59,65,67,72,75,76,79,84,87,90,92,94,97,99,102,104,107,108,111,114,116,119,120,122,124,127,132],
 * [47,55,59,62,66,68,74,78,80,82,85,88,93,96,99,101,102,105,106,108,110,113,115,118,120,121,124,127,130,133],
 *
 *
 *
 * 22,
 * [[0,1,3,4,5,7,8,11,13,15,18,21,24,27,30,32,35,36,39,41,42,43,46,49,52,55,58,60,63,66,67,69,72,75,78,80,81,82,85,86],
 * [1,4,6,8,11,12,15,17,18,20,23,24,27,30,33,34,38,39,42,44,47,48,51,52,55,57,59,62,64,67,70,72,75,77,81,83,84,87,90,91],
 * [4,7,8,11,14,16,18,20,21,24,27,29,32,35,36,39,40,42,44,46,49,52,54,56,58,60,61,64,67,70,73,76,78,81,84,87,89,91,93,96],
 * [5,8,10,13,15,19,21,23,24,27,29,31,34,37,38,41,43,45,46,49,52,55,58,59,61,64,67,69,71,72,76,78,79,83,87,90,91,94,96,97],
 * [6,11,14,16,18,22,24,27,29,32,33,35,36,40,42,44,47,50,51,52,54,58,60,62,64,67,70,73,76,79,82,84,87,88,91,94,97,99,101,102],
 * [9,13,16,19,21,23,25,29,31,35,38,39,42,45,48,51,54,56,57,60,63,64,67,69,72,73,74,76,79,81,85,88,90,92,95,98,100,101,104,106],
 * [10,16,19,22,24,26,29,31,34,36,40,41,45,46,50,54,56,59,60,63,66,69,70,72,75,77,79,81,83,85,88,91,93,96,98,99,102,105,107,109],
 * [12,18,22,25,26,29,32,33,37,39,42,44,47,50,52,57,59,61,62,66,68,71,72,74,76,80,82,84,87,90,92,94,95,98,101,102,105,107,109,112],
 */
public class TwoArrayFind {
    public static void main(String[] args) {
        int arr[][] = new int[][]{
                {0,1,3,4,5,7,8,11,13,15,18,21,24,27,30,32,35,36,39,41,42,43,46,49,52,55,58,60,63,66,67,69,72,75,78,80,81,82,85,86},
                {1,4,6,8,11,12,15,17,18,20,23,24,27,30,33,34,38,39,42,44,47,48,51,52,55,57,59,62,64,67,70,72,75,77,81,83,84,87,90,91},
                {4,7,8,11,14,16,18,20,21,24,27,29,32,35,36,39,40,42,44,46,49,52,54,56,58,60,61,64,67,70,73,76,78,81,84,87,89,91,93,96},
                {5,8,10,13,15,19,21,23,24,27,29,31,34,37,38,41,43,45,46,49,52,55,58,59,61,64,67,69,71,72,76,78,79,83,87,90,91,94,96,97},
        };
        System.out.println(Find(102,arr));
    }


    //超时了
    public static boolean Find(int target, int [][] array) {
        int j=0;
        for(int i=0;i<array.length;){
            for(;j<array[0].length;){
                if(target==array[i][j]){
                    return true;
                }else if(target>array[i][j]){
                    j++;
                }else {
                    if(j>0)
                        if(target<array[i][j]&&target>array[i][j-1]){
                            j--;
                            i++;
                        }else{
                            j--;
                        }
                    break;
                }
            }
            if(j==array[0].length && target>array[i][array[0].length-1]){
                i++;
            }else if(j==array[0].length&&target==array[i][array[0].length-1]){
                return true;
            }else if(j==array[0].length&&target<array[i][array[0].length-1]){
                j=j-2;
            }
        }
        return false;
    }
}
